package demo1;

import javax.print.DocFlavor;
import java.util.HashMap;
import java.util.Random;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    //排序数组  （快速排序）
    public int[] sortArray(int[] nums) {
        qsort(nums,0,nums.length-1);
        return nums;
    }

    private void qsort(int[] nums,int l, int r){
        if(l>=r) return;

        int key = nums[new Random().nextInt(r-l+1)+l];
        int i = l; int left = l-1; int right = r+1;
        while (i < right) {
            if(nums[i]<key)  swap(nums,++left,i++);
            else if(nums[i]==key) i++;
            else swap(nums,i,--right);
        }

        qsort(nums,l,left);
        qsort(nums,right,r);
    }

    private void swap(int[] nums, int i,int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    //颜色划分
    public void sortColors(int[] nums) {
        int n = nums.length;
        for(int left=-1,right=n,i=0;i<right;){
            if (nums[i] == 0) {
                int tmp = nums[++left];
                nums[left] = nums[i];
                nums[i++] = tmp;
            }else if(nums[i]==1){
                i++;
            }else {
                int tmp = nums[--right];
                nums[right] = nums[i];
                nums[i] = tmp;
            }
        }
    }


    //抓青蛙
    public int minNumberOfFrogs(String croakOfFrogs) {
        char[] c = croakOfFrogs.toCharArray();
        String t = "croak";
        int[] hash = new int[5];
        HashMap<Character,Integer> map = new HashMap<>();
        for(int i =0;i<t.length();i++){
            map.put(t.charAt(i),i);
        }
        for (int i = 0; i < c.length; i++) {
            if (c[i] == 'c') {
                if (hash[map.get('k')] > 0) {
                    hash[map.get('k')]--;
                    hash[0]++;
                }else hash[0]++;
            }else {
                int index = map.get(c[i]);
                hash[index]++;
                hash[index-1]--;
            }
        }
        for (int i = 0; i < 4; i++) {
            if(hash[i]!=0) return -1;
        }
        return hash[4];
    }

    public static void main1(String[] args) {
        countKConstraintSubstrings("10101",1);
    }

    //统计满足k约束的子字符串数量 1
    public static int countKConstraintSubstrings(String s, int k) {
        if(k==0) return 0;
        //HashMap<Character, Integer> map = new HashMap<>();
        int n = s.length();
        int count = 0;
        for (int i = 0; i < n; i++) {
            int[] hash = new int[2];
            for (int j = i; j < n; j++) {
                int ret = s.charAt(j)=='0' ? hash[0]++ : hash[1]++;
                if(hash[0]>k && hash[1]>k) break;
                count++;
            }
        }
        return count;
    }
}


















